We consider relational databases organized over an ordered domain with some additional relations — a typical example is the ordered domain of rational numbers together with the operation of addition. In the focus of our study are the first-order queries that are invariant under order-preserving “permutations” — such queries are called order-generic. It has recently been discovered that for some domains order-generic FO queries fail to express more than pure order queries. For example, every order-generic FO query over rational numbers (...) with + can be rewritten without +. For some other domains, however, this is not the case.We provide very general conditions on the FO theory of the domain that ensure the collapse of order-generic extended FO queries to pure order queries over this domain: the Pseudo-finite Homogeneity Property and a stronger Isolation Property. We further distinguish one broad class of domains satisfying the Isolation Property, the so-called quasi-o-minimal domains. This class includes all the o-minimal domains, but also the ordered group of integer numbers and the ordered semigroup of natural numbers, and some other domains.An important difference of this paper from the recent series of related papers is that we generalize all the notions to the case of finitely representable database states — as opposed to finite states — and develop a general lifting technique that, essentially, allows us to extend any result of the kind we are interested in, from finite to finitely representable states. We show, however, that these results cannot be transfered to arbitrary infinite states. (shrink)

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than with defining (...) a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. (shrink)